Optimal and Suboptimal Detection of Gaussian Signals in Noise: Asymptotic Relative Efficiency

Optimal and Suboptimal Detection of Gaussian Signals in
Noise: Asymptotic Relative Efficiency

Youngchul Sung*^, Lang Tong° and H. Vincent Poor^^

'^School of Electrical and Computer Engineering, Cornell University, Ithaca, NY 14850
''Dept. of Electrical Engineering, Princeton University, Princeton, NJ 08544

ABSTRACT

The performance of Bayesian detection of Gaussian signals using noisy observations is investigated via the error
exponent for the average error probabiUty. Under unknown signal correlation structure or limited processing
capability it is reasonable to use the simple quadratic detector that is optimal in the case of an independent
and identically distributed (i.i.d.) signal. Using the large deviations principle, the performance of this detector
(which is suboptimal for non-i.i.d. signals) is compared with that of the optimal detector for correlated signals
via the asymptotic relative efficiency defined as the ratio between sample sizes of two detectors required for the
same performance in the large-sample-size regime. The effects of SNR on the ARE are investigated. It is shown
that the asymptotic efficiency of the simple quadratic detector relative to the optimal detector converges to one
as the SNR increases without bound for any bounded spectrum, and that the simple quadratic detector performs
as well as the optimal detector for a wide range of the correlation values at high SNR.

Keywords: Quadratic detector, error exponent, large deviations principle, asymptotic relative efficiency (ARE)

1. INTRODUCTION

We consider in this paper the optimal and suboptimal detection of stationary Gaussian signals using noisy
observations yi under a Bayesian formulation. The corresponding null and alternative hypotheses are given by

Hq : y,= w,, z = 1,2, • • • ,n,
Hi : yi ^ Wi + 6si, i ^ 1,2,- ■■ ,n,

where {wi} is independent and identically distributed (i.i.d.) A/'(0,(t^) noise with a known variance cr^, is a
nonnegative constant, and {si} is a zero-mean unit-variance stationary Gaussian signal with spectrum /s(w),
independent of the noise {wi}. The prior probabilities for the hypotheses are denoted by

TTo^Pr{Ho}, 7ri=Pr{i7i} = l-7ro. (2)
Due to the stationarity of the signal, the signal-to-noise ratio (SNR) for the observations is constant and is given

by

SNR = (3)

Such a model arises, for example, in sensor networks (see, e.g.. Sung et al}^'^^). For a large sensor network
deployed for the detection of stochastic signals such as gases or particles in a fixed area, it is reasonable to
assume that the signal is random and that spatial signal samples are correlated, while the measurement noise is
independent from sensor to sensor. Typically, the optimal detector for (1) is given in the form of a quadratic
detector that uses the correlation structure and requires the joint processing of all signal samples. In general,
optimal detection using n samples requires O(n^) multiplications and 0{n) memory size for storing past samples
except in some cases where recursive techniques are available.^ These processing requirements may be prohibitive
in applications such as sensor network in which each sensor node has stringent energy and storage constraints

fFurther author information: Send correspondence to H. Vincent Poor. E-mail: poor@princ6ton.edu

and the mimbcr of nodes (or observation samples) is large. Thus, one can consider other detector structures
with reduced complexity, e.g., simple quadratic detectors or banded-quadratic detectors.^'®

In this paper, we are interested in the asymptotic performance of these detectors and the performance
comparison between them using the asymptotic relative efficiency (ARE) derived from the large deviations
principle (LDP).^ Poor and Chang investigated the performance of these detectors using Pitman's ARE or
asymptotic deflection ratio.^'^'* While ARE from the large deviations principle is based on the law of large
numbers, Pitman's ARE relies on convergence in distribution (of the test statistics). Thus, these two ARE's do
not necessarily provide the same order for the performance of two detectors under consideration, and Pitman's
ARE generally provides more accurate results than that of LDP in the low SNR regime.^ However, Pitman's
ARE is based on the asymptotic local scenario wherein the signal power decreases to zero with a certain rate,
i.e., typically 9 in (1) decreases as for ft, > as the number n of samples increases. Thus, it does not

allow the performance comparison for a fixed signal- to- noise ratio (SNR). Poor and Chang considered the locally
optimal detector as the reference detector under the Neyman-Pearson formulation. (The efficacy* of the optimal
quadratic detector is difficult to obtain since the amplitude parameter 6 is inseparable in the optimal test statistic,
as shown in (14)).

The LDP for stationary Gaussian processes is well-established. ^^"^^ Based on the result of Bryc and Dembo,^^
here we extend the work of Poor and Chang'"' ^ and compare the relative performance of several quadratic
detectors using the ARE from the LDP, focusing on the effects of SNR on the ARE with the optimal detector
as the reference detector under a Bayesian formulation.

The paper is organized as follows. In Section 2, some relevant results concerning the LDP are presented. In
Section 3, the quadratic detectors that we consider and the corresponding ARE are provided. In Section 4, some
numerical results are presented for several examples of signal correlation, followed by the conclusion in Section
5.

2. PRELIMINARIES

In this section, we present some definitions and results concerning LDP relevant to the further development.

Definition 2.1 (Large deviations principle^^). Let {P„} be a sequence of prohahility distributions
defined on {Pn} is said to satisfy the large deviation principle with a rate function I : X ^ [0,oo] if

• the level sets 7~^([0, c]) are compact for all c < oo,

limsup — log P„(C) < — inf I{x) V closed C &

n — ^oo ri x^C

• and

lim inf - log P„ (O) > - inf I(x) V open O ^T.

For the probability distributions governing a sequence of sample means the LDP is given by Cramer's theorem,
and its extension to general sequences of random variables is provided by the Gartner-Ellis theorem based on
the convergence of cumulant generating functions. In particular, for the sequence of quadratic functionals
of Gaussian processes the rate function is derived by Bryc and Dembo"'^^ circumventing difficulties in applying
the Gartner-Ellis theorem to this problem, which is summarized in the following theorem.

Theorem 2.2 (Bryc and Dembo^^). Let {Yi, ~oo < i < oo} be a (real-valued) zero-mean stationary
Gaussian process with bounded spectral density function Syico) defined as

oo

Sy{u;)= J2 E{Fon}e-^'" (4)

k=—oo

* Pitman's ARE is expressed by the ratio of the efficacy of one detector to that of the other.

with essential supremum M. Let a random variable = {\Y^=\^i \ ^'^'^ be the distribution of Zn, i.e.,
Pn{S) = Pr{Zn G S} for S G B{M.). Then, {P„} satisfies the LDP with a rate function

I{z)= sup [zt-K{t)], (5)

where

1 f^""

A{t) = -— J log(l - 2tSy{uj))duj (6)

Lemma 2.3 (Bryc and Dembo^^). Suppose Y = [Yi, ■ • • , V^]^ is a real-valued zero-mean Gaussian vector
luith the covariance matrix S and let W be a symmetric real-valued n x n matrix. Then, with Ai , • • • , A„ the
eigenvalues of the matrix WS we have

i=l

for allsGC s.t. maKi{Re{s)Xi} < 1/2. FuHhermore, log Ee*^'^'^'^ = oo for alltGR s.t. maxi{tXi} > 1/2.

Another useful result concerns the asymptotic distribution of the eigenvalues of a ToepHtz matrix, which is
summarized in the following theorem.

Theorem 2.4 (Grenander and Szego^). Let Sy{uj) be the spectrum of {Yi}, defined as (4), with finite
lower and upper bounds denoted by m and M, respectively. Let be a covariance matrix defined as

S,,„ = [E{YiYj}]lj^, (7)
X^^\ ■ ■ ■ , An"^ be the eigenvalues of Then, for any continuous function h : [m, M] M, we have

hm 1 f2 '^(^i"^) = T- r KSy{'^))d^. (8)

3. ASYMPTOTIC RELATIVE EFFICIENCY

In this section, we present the classes of detectors that we consider and their corresponding rate functions. By
stacking the observations and corresponding signals and noises, the hypotheses (1) can be rewritten in vector
form as

Hq : y„ = w„, , ,

Hi : Yn =w„ + 6's„,

where

Yn = [yo, • • • ,yn]^, Sn = [so, ■ ■ ■ , Sn]"^ , = [wq, ■ ■ ■ , Wn]"^ ,

and the noise vector w„ ~ A/'(0, cr^I), s„ ~ Af{0,'Ss,n), and y„ has distribution A/'(0,Sj,„) for hypothesis j
(j = 0, 1) where

So,„ = a2l, SLn^a^I + e^-E.^n- (10)
For convenience, we further assume equal prior probabilities, i.e.,

TTO = TTl = ^. (11)

Then, the optimal detector for (9) is given by the maximum a posteriori probabiUty detector:

5o{yn)

1, ilogL„(y„) >r = 0,
0, otherwise,

(12)

where

and

Ln{yn)

1/2

gjy^QnYn

(13)

(14)

Since the calculation of the likelihood ratio requires the product of all observations, the optimal detector

typically requires 0{n^) multiplications and 0{n) memory for the storage of the previous samples/ Next, we
consider a simple quadratic detector obtained by neglecting the signal correlation, i.e., „ = I, and it is given

by

ilogk^^^V^'ei^nQny.

^sg(yn)

otherwise.

>0,

where

a2(a2 + 02)

The test statistic in this case can be rewritten as

(15)

(16)

Tsq,n = log

+

(17)

Thus, the simple quadratic detector requires 0{n) multiplications and one storage for accumulation.

We also consider a banded-quadratic detector structure which has intermediate complexity between the opti-
mal and the simple quadratic detector, similar to that considered by Poor and Chang.''' ^ Since the determinants
of the two matrices So,n and can be computed off line for the optimal detector (12, 13) when the signal
correlation structure is known beforehand, the main complexity results from the calculation of the quadratic
term based on observations. Thus, a class of detectors with intermediate complexity is given by

ilogL^'")(y„)>0,
otherwise.

(18)

where

1^0, n|

1/2

62

(19)

and qI™^ is a banded n x n symmetric positive-definite Toeplitz matrix with bandwidth (2m -|- 1), i.e.

6o bi
bi bo

bi
bo

bi bo
■•• 6i

bi :
bo bi
bi bo

(20)

Here, the values of hi, / = 0. 1, • • • , m = bi) need to be properly determined for optimal performance. Let
the discrete-time Fourier transform of the finite sequence {b-m, b-m+i, ■ ■ ■ ■, b-i,bo, bi, - ■ ■ , bm} be gm{ijj), i.e.,

m

5„(a;) =6o + 2^6,cos(/a;), < w < 27r. (21)
1=1

Then, the eigenvalues of converge to uniform samples, {gm{^^)}k=o,i,— ,n-i) of 5m('^) as n increases since
qI™^ is Toeplitz.9

3.1. Error Exponent and ARE

The false alarm probability, , and the miss probability, (3n^ , for a particular detector 6 are defined as

^ Pr{%„) = l|ifo}, (22)
/3W = Pr{5(y„) = 0|ifi}. (23)

In general, these probabilities decay exponentially as n increases without bound, and the decay rate is given by
Theorem 2.2. Thus, we have

Eo{S) ^ - lim iloga(f)= inf 4'^(^), (24)

n->(X) n ze[0,oo)

Ei{S) = ~ \im -\og(3^J^ = inf 4^\z), (25)

n^oon " ze(-oo,0) ^ ^ ^' ^ '

where Ij{5){z), j = 0, 1, is defined as (5) with limiting cumulant moment generating function A'j^^t) correspond-
ing to the considered detector and hypothesis. The error exponent or the exponential decay rate of the average
error probability for the detector S is given by

E{S) ^ \im -- log Pit] = lim - i log(7roa(f ) + tti/S^*) ) ,

n— >oo n rx— >(X) n

= mm{Eo{6),Ei{6)}. (26)

Hence, we have asymptotically

-^e-"-^(*). (27)

Eq. (27) provides an asymptotic criterion for the comparison of two detectors.^ The efficiency of {Si} relative
to {62} for sample size n is defined to the ratio n2/n, where 712 is the smallest number of samples such that
Pe^nl < Pefn^ Thus, the asymptotic efficiency of a detector relative to another detector 62 from the LDP is
defined as the ratio between the two error exponents:

Now let us consider the rate function for each detector under consideration. For the simple quadratic detector
^sg(yn) the calculation of the rate function under each hypothesis is straightforward from Theorem 2.2. Applying
Theorem 2.2 to (17), we have

where /s(w) is the spectrum of the signal and the range of t is defined for each case so that the term in the
logarithmic function is strictly positive.

For the optimal detector 6o{-) the test statistic is given by

To,„ = - log
n

1/2

(31)

In this case the rate function is obtained by a whitening transform. Let the eigendecomposition of the signal
covariance matrix Ss^„ be

= UAU^ = Udiag(A("\ • • • , A(r))U^,

where U is an orthogonal matrix. Then, the eigendecomposition of Q„ is given by

Q„ = USU^,
= Udiag

(32)
(33)

2\(«)

2\(«)

An

and

where y„ = S^/^U^y„ and yi is the i^^ element of y„. Thus, the test statistic is given by

(34)

1 " 1 "

By Theorems 2.2 and 2.4, we have
A^)(t)

2ir

2-n-

log 1 - 1

(35)
(36)

The range of t is again defined for each case so that the term in the logarithmic function is positive. For
the optimal case the rate function for the quadratic part has also been derived by several other authors, e.g.,
Chamberland.^^

For the banded quadratic detector the test statistic is given by

'5,n

■log

-'0,n|

1/2

a

c72 + ^2;^(") 2n

— + — v^O'^V

(37)

where Qn'"'' is defined in (20). By Lemma 2.3, the cumulant generating function for the quadratic part under
the hypothesis j is given by

1 "

logE,{e*^''""Q^"'^"} = X^log (l - iA(;)) , j = 0, 1,

(38)

for all t < 1/ (maxi A^J-* ) , where {x[j\i = I,--- , n} are the eigenvalues of Ql^'s^-^n, and ^j,n (j = 0,1) is
defined in (10). Because of the Toeplitz structure of Qn™^ and it follows that^

1 1 /"Z-TT

(39)

for any continuous function h{-), where ,fj{uj) is the spectnun of the observation process {j/j} under the hypothesis
j U = 0, 1). Thus, the rate function for the banded-quadratic detector is given by

where gm{^) is defined in (21) and the range of t is defined properly in each case.

4. EXAMPLES AND NUMERICAL RESULTS

Wc now consider some signal examples and investigate the relative performance of the detectors in the previous
section as a function of various parameters such as correlation strength and SNR via the asymptotic relative
efficiency defined in (28). In particular, we consider Gauss-Markov signals and triangularly correlated signals.
Except for some simple cases such as autorcgrcssivc signals without additive noise-'^'' it is difficult to obtain
closed-form expressions for the rate functions in the previous section. Thus, we evaluate the rate and ARE by
numerical evaluation of the error exponent.

4.1. Gauss-Markov Signal

We first consider the stationary Gauss-Markov signal for which the correlation is given by

¥.{SoSk} ^ o}^\ /c = 0,±1,±2, ••• ,(0 < a < 1), (42)
and the spectrum is given by the Poisson kernel:

1 — 2acosa; -|- a''

Fig. 1 (a) shows the error exponent for the false alarm and miss probabilities for the optimal and simple
quadratic detectors as a function of the correlation strength a at 10 dB SNR. It is seen that the error exponent
Eo{5sq) for the false alarm probability of the simple quadratic detector is independent of the correlation strength
and is equal to the maximum value of the error exponent of the optimal detector achieved by independent
signal'!' (a = xhis is easily seen by the logarithmic generating function (29) which does not depend on the
signal spectrum. However, the error exponent Ei{5sq) for the miss probability is less than that of the false alarm
probability for all values of a, and decreases to zero as the signal correlation becomes strong (a — » 1). Thus,
the error exponent for the average error probability is determined by that of the miss probability for the simple
quadratic detector. On the other hand, the error exponents for the false alarm and miss probabilities are the
same, i.e., Eo{5o) = E\{5o), for the optimal detector with equal prior probabilities, i.e., zero threshold in (12).
In this case, the minimum in (26) is attained and the error exponent is the ChernofF information between the
two distributions under the hypotheses (9). Note that the error exponent for the miss probability of the simple
quadratic detector is smaller than that of the optimal detector for < a < 1. So, the error exponent of the simple
quadratic detector is smaller than that of the optimal detector even if the simple quadratic detector performs
better than the optimal detector for the false alarm probability. Prom the detector structure (17) one can see
that the simple quadratic detector is optimized for the detection of the false alarm event regardless of the signal
correlation, thereby sacrificing the performance for correct detection, while the optimal detector optimizes the
test statistic so that it can perform equally well for both of the false alarm and miss events.

Pig. 1 (b) shows the ARE of the simple quadratic detector to the optimal detector as a function of correlation

strength a for several values of SNR (0, 10, 20, 30 dB). It is seen that at weak correlation the simple quadratic
detector performs as well as the optimal detector for all the values of SNR. It is also seen that the ARE decreases

^This is not the case when the SNR is low. At low SNR the maximum value of the error exponent for the optimal
detection is achieved at some correlation value < o < 1.^°

(a) (b)
Figure 1. Optimal and simple quadratic detectors (Gauss-Markov signal): (a) error exponent, Ej{5), j = 0,1, as a
function of correlation strength a (SNR=10dB) and (b) ARE as a function of correlation strength a for SNR — 0, 10, 20,
30 dB.

to zero eventually as the correlation becomes strong (a ^ 1). This is because for the perfectly correlated signal
(a = 1) the optimal test statistic is in form of (X]"=i Vi)'^ which uses the perfect signal correlation and adds the
signal component coherently before taking the magnitude by squaring. On the other hand, the test statistic
(17) for the simple quadratic detector neglects this correlation entirely. It is seen that the range of correlation
values over which the simple quadratic detector performs as well as the optimal detector increases as SNR
increases. Note that at an SNR of 30 dB the simple quadratic detector performs as well as the optimal detector
through almost the whole range of correlation except the very highly correlated case (0.9 < a < 1). The behavior
of ARE as a function of SNR is summarized in the following proposition.

Proposition 4.1. The ARE of the simple quadratic detector (15) to the optimal detector (12) increases to unity
for any hounded spectrum fs{^) as SNR increases without hound.

Proof: Since the error exponent for the simple quadratic detector is determined by the miss probability and the
optimal detector has the same error exponent for the false alarm and miss probabilities, this can be shown via
the cumulant generating functions (30, 36) for the two detectors. For any bounded spectrum we have

fs{uj)<M, V0<w<27r, (44)

for some M > 0. So, we have for the second term in (30), as 9^ oo,

e\a^ + e^fs{uj)) e^fsioj)

which is the corresponding term in (36). For the first terms in (30) and (36) we have

(45)

log 9 . n9 log — (46)

log ^"THJT^'^'^ ^ / log 02 f i ^ = log "H2 ' 47)

since f^^ log fs{uj)diLj = because of the para-Hermitian conjugacy of the spectral factorization of /^(i^) =
L(z)L*(4r)|z=eJ'^ • Thus, the two rate functions for the simple quadratic and the optimal detectors converge as
02 ^ 00.^ ■

For the spectrum (43) we have bounded spectrum for any fixed value of a (0 < a < 1), which explains the
behavior of the ARE in Fig. 1 (b) as SNR increases.

4.2. Triangularly Correlated Signal

Next we consider the stationary signal with triangular correlation, i.e.,

V{q q \ -f ^-\k\/M, \k\<M

nSoSk} - I 0^ > (48)

where M > is the correlation length of the signal. The spectrum of the signal is given by the Mth Fejek
kernel'':

, , , 1 /sin(Mw/2)\^ , ,

M \ sin(w/2) /

Fig. 2 (a) shows the error exponent for the false alarm and miss probabilities for the optimal and simple
quadratic detectors as a function of the correlation width M at 10 dB SNR for the triangularly correlated signal.
Similar relative behavior to that in the Gauss-Markov signal case is observed. It is worth noticing that the error
exponents for the two detectors decay sharply near Af = 1 as the correlation length M increases, and the decay
is mild as M further increases.

5 10 15 20 25 30 5 10 15 20 25 30

M M

(a) (b)
Figure 2. Optimal and simple quadratic detectors (triangularly correlated signal): (a) error exponent, Ej{S), j — 0, 1,
as a function of correlation strength a (SNR=10dB) and (b) ARE as a function of correlation strength a for SNR = 0,
10, 20, 30 dB.

Fig. 2 (b) shows the ARE of the simple quadratic detector to the optimal detector as a function of correlation
strength a for the same values of SNR as in the Gauss-Markov case. It is seen that the ARE increases as SNR
increases as expected from Proposition 4.1. However, at an SNR of 30 dB there exists noticeable performance
degradation for the simple quadratic detector compared with Fig. 1 (b) for a wide range of the correlation length
M.

4.3. Banded Quadratic Detector

We here provide some necessary conditions for the optimal qI™'' in (19) and evaluate the performance of the
banded quadratic detector. The test statistic (37) has two different limits (as n — > oo) under the two hypotheses,
and they are given by

rr " lim{TZ'\Ho}^- log , dL. + - / a'aMdco, (50)

r(") ^ hm {T^r^lTJi} = ^ r log + ^ /'V' + 0'M^))9Mdcj. (51)

The first term in each equation is by applying Theorem 2.4, and the second term follows from the law of large

numbers and iEj{y^Qi"'Vn} = :^tr{Qi™^Sj,„} = ^ J2i=i ^ij'' (to which (39) is applied) since the trace of a

matrix is the sum of its eigenvalues. From (50, 51) we have Tq™^ < T^"'^ for any 9 > and a signal spectrum
which is not identically zero. One necessary condition for the optimal gm{^^) is given by

Tq^™) < T (= 0) < Ti^"\ (52)

Otherwise, the error exponent E{6b,m) is zero and the average error probability of the banded-quadratic detector

decays at subcxponcntial rate as n increases. For example, if Tg™-* > 0, then Eo^S^.m) = infze[o,oo) -'"o' '" (-^) ~ ^
since /q'''" (Tq™'') — 0. Similarly, we have i?i((5h,„i) = inf^£(_co,o) if'''"^ (z) = if T^"^^ < 0. Thus, in the case of
m = we have gm{'^) = and it is seen from (51) that the optimal bo is positive (otherwise, T^^^ < 0), which is
consistent with our assumption of the positive-definiteness of Qn"^ . In general, it is easy to see that well chosen
^0) • • • satisfy the condition (52) since the first terms in (50, 51) arc equivalent and negative. When (52) is
satisfied, it is known that the infimum for the rate function is achieved at the decision threshold, i.e.,

Eo{Sh,m) = inf /o'''-(^)=/o'""'(0)= sup {-A^-(i)}, (53)

zS 0,oo) . ^ f 1 1

-00<t<mfo<„<2„{^;^^i(^|

Ei{db,m) = inf /^-(^)=J^-(0)= sup {-Af""(t)}, (54)

zGl — 00,0) . ,. f , 1

where Ao''-'"(i) and A7'"'(t) are given by (40) and (41), respectively, and the optimal values of t for (53) and
(54) are given by solving

and

respectively. Thus, the optimal gm{<^) for given m, SNR and signal spectrum is obtained from the following
optimization problem:

g*M = argmax|min{/o''-(0),/^-(0)}| (57)

under the constraint (52). A closed-form expression for (57) seems difficult to obtain in general cases. How-
ever, (52-56) facilitate numerical approaches to the optimization problem, and a procedure using grid search is
summarized in Fig. 3.

Wc considered the Gauss-Markov signal (43) and evaluated the banded-quadratic detector with m = 1 which
corresponds to the case that each sensor requires the information only from a neighboring sensor in a wireless
sensor network setup, as shown in Fig. 4. Fig. 5 (a) shows the error exponents EQ{5bs) and E\{5b,i) of the
banded-quadratic detector optimized using the algorithm shown in Fig. 3 for each value of a at 10 dB SNR. Fig.
5 (b) shows the corresponding ARE of the banded-quadratic detector to the optimal detector. For a SNR of
dB SNR the banded-quadratic detector with m = 1 performs well not only in the low correlation values but also
in the high correlation region where the performance of the simple quadratic detector degrades severely (see Fig.
1 (b)). Surprisingly, it is seen that optimal performance is almost achieved with only m = 1 for a SNR of 10 dB.

5. CONCLUSIONS

We have considered the relative performance of several quadratic detectors for Gaussian signals in Gaussian noise
under a Bayesian formulation. Using the large deviations principle, a general form of the rate function for the
simple quadratic detector, optimal detector, and banded-quadratic detector has been provided using the signal
spectrum. For the examples of Gauss-Markov and triangularly correlated signals we have evaluated the error
exponents for the false alarm and miss probabilities and the ARE for the average error probability. We have also
investigated the effects of SNR on the relative performance. The asymptotic efficiency of the simple quadratic

Read (60

; ' ' ' J bm)

Compute (50) and (51)

Compute /o' " (0) and /i" '" (0)
by optimization of (53,54)
using (40,41,55,56)

E ~ minl/p'' '
Store (60,

^(0),/^-(0)}
■ ■ ,bm,E)

Figure 3. An optimization algorithm (grid search).

Sensor i

Vi-i

1

Vi

Figure 4. Banded-quadratic detector with m = 1: Distributed computation in wireless sensor network (Co ~ boyf).

0.2 0.4 0.6 0.8 1 0.2 0.4 0.6 0.8 1

a a

(a) (b)

Figure 5. Banded-quadratic detector (Gauss-Markov signal): (a) error exponent, Ej{S), j — 0,1, as a function of
correlation strength a for SNR = 10 dB and (b) ARE as a function of correlation strength a with the optimized gm{i-o)
(SNR = 0, 10 dB).

detector relative to the optimal detector converges to \inity as SNR increases without bound for any bounded
signal spectrum. At high SNR the simple quadratic detector performs as well as the optimal detector for a wide
range of correlation values and the banded-quadratic detector effectively achieves the optimal performance with
much lower complexity.

ACKNOWLEDGMENTS

This work was supported in part by the Multidisciplinary University Research Initiative (MURI) under the Office
of Naval Research Contract N00014-00-1-0564. Prepared through collaborative participation in the Communi-
cations and Networks Consortium sponsored by the U. S. Army Research Laboratory under the Collaborative
Technology Alliance Program, Cooperative Agreement DAAD19-01-2-0011.

The work of H. V. Poor was supported in part by the Office of Naval Research under Grant N00014-03-1-0102.

REFERENCES

1. H. V. Poor, An Introduction to Signal Detection and Estimation, 2nd Edition, Springer, New York, 1994.

2. A. W. van der Vaart, Asymptotic Statistics, Cambridge University Press, New York, 1998.

3. J. Capon, "On the asymptotic efficiency of locally opitmum detectors," IRE Transactions on Information
Theory, vol. 7, pp. 67-71, Apr. 1961.

4. H. Chernoff, "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations,"
Annals of Mathematical Statistics, vol. 23, pp. 493-507, no. 4, Dec. 1952.

5. C. R. Baker, "Optimum quadratic detection of a random vector in Gaussian noise," IEEE Transactions on
Communication Technology, vol. COM-14, no. 6, pp. 802-805, Dec. 1966.

6. F. C. Schweppe, "Evaluation of likelihood functions for Gaussian signals," IEEE Transactions on Information
Theory, vol. IT-1, pp. 61-70, 1965.

7. H. V. Poor and C. Chang "A reduced-complexity quadratic structure for the detection of stochastic signals,"
Journal of the Acoustical Society of America, vol. 78, no. 5, pp. 1652-1657, Nov. 1985.

8. C. Chang and H. V. Poor, "A note on memory length and the detection of Gaussian signals," Proceedings of
the 1983 Conference on Information Sciences and Systems, The Johns Ifopkins University, Baltimore, MD,
pp. 539-543, Mar. 1983.

9. U. Grenander and G. Szego, Toeplitz Forms and Their Applications, University of California Press, Berkeley,
CA, 1958.

10. F. den Hollander, Large Deviations (Fields Institute Monographs, 14), American Mathematical Society,
Providence, RI, 2000.

11. A. Dembo and O. Zeitouni, Large Deviations Techniques and Applications, Jones and Bartlett, Boston, MA,
1993.

12. M. D. Donsker and S. R. S. Varadhan, "Large deviations for stationary Gaussian process," Communications
in Mathematical Physics, vol. 97, pp. 187-210, 1985.

13. W. Bryc and A. Dembo, "Large deviations for quadratic functionals of Gaussian processes," Journal of
Theoretical Probability vol. 10, no. 2, pp. 307-332, 1997.

14. W. Bryc and W. Smolenski, "On the large deviation principle for a quadratic functional of the autoregressive
process," Statistics and Probability Letters, vol. 17, pp. 281-285, 1993.

15. B. Bercu, F. Gamboa, and A. Rouault, "Large deviations for quadratic forms of stationary Gaussian pro-
cesses," Stochastic Processes and their Applications, vol. 71, pp. 75-90, 1997.

16. G. R. Benitz and J. A. Bucklew, "Large deviation rate calculations for nonlinear detectors in Gaussian
noise," IEEE Transactions on Information Theory, vol. 36, no. 2, pp. 358-371, Mar. 1990.

17. J.-F. Chamberland, Design of Sensor Networks for Detection Applications via Large- deviation Theory, Ph.D.
Dissertation, University of Illinois at Urbana-Champaign, 2004.

18. Y. Sung, L. Tong, and H. V. Poor, "A large deviations approach to sensor scheduling for detection of
correlated random fields," in Proceedings of 2005 IEEE International Conference on Acoustics, Speech, and
Signal Processing, Philadelphia, PA, Mar. 2005.

19. Y. Sung, L. Tong, and H. V. Poor, "Sensor configuration and activation for field detection in large sensor
arrays," in Proceedings of the Fourth International Symposium on Information Processing in Sensor Networks,
Los Angeles, CA, Apr. 2005.

20. Y. Sung, L. Tong, and H. V. Poor, "Ncynian-Pcarson detection of Gauss-Markov signals in noise: Closed-
form error exponent and properties," in Proceedings of 2005 IEEE International Symposium on Information
Theory, Adelaide, Australia, Sep. 2005.